package sol.leetcode;

/**
 * Search a 2D Matrix
 */
public class Issue074 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int[] firstCol = new int[matrix.length];
        for (int i = 0; i < matrix.length; ++i)
            firstCol[i] = matrix[i][0];
        int row = binarySearch(firstCol, target);

        if (row == -1)
            return false;
        if (matrix[row][0] == target)
            return true;

        int col = binarySearch(matrix[row], target);
        if (matrix[row][col] == target)
            return true;

        return false;
    }

    private int binarySearch(int[] nums, int target) {
        int start = 0, end = nums.length - 1, mid;

        while (end - start > 1) {
            mid = (start + end) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) end = mid - 1;
            else start = mid;
        }
        return nums[end] <= target ? end : start;
    }

    public static void main(String[] args) {
        int[][] nums = {{1, 3},{4,6}};
        Issue074 sol = new Issue074();
        System.out.println(sol.searchMatrix(nums, 0));
    }
}
